Automatic routing of VLSI chips, modules or cards can be accomplished by a variety of methods, many of which have been known and studied for at least 20 years. It is acknowledged by practitioners that automatic routing consists of two stages: a Global Routing, which produces rough locations of wires, and a Detailed Routing, which takes the results of the global routing to generate detailed locations and layers for wiring the chip.
Automatic routing has been enhanced by taking into consideration certain relevant factors which improve the electrical characteristics of the package being wired. Some of these techniques have been described in the literature, examples of which are listed below:
S. Y. Kuo, "YOR: an yield optimizing routing algorithm by minimizing critical areas and vias," published in the IEEE Transactions on CAD, Vol. 12, No. 9, pp 1303-1311, September 1993; PA1 Z. Chen and I. Koren, "Layer assignment for yield enhancement", IEEE International Workshop on Defect and Fault Tolerance in VLSI Systems, November 1995, pp 173-180; PA1 Pitaksanonkul et. al., "DTR: A Defect Tolerant Routing Algorithm", Proceedings of 26st Design Automation Conference, pp 795-798, 1989; PA1 A. Venkataraman, H. H. Chen and I. Koren, "Yield enhanced routing for high-performance VLSI designs", Proceedings of SPIE Conference on Microelectronic Manufacturing Yield, Reliability, and Failure Analysis, pp 50-60, October 1-2, 1997; PA1 T. G. Waring, G. A. Allan and A. J. Walton, "Integration of DFM Techniques and Design Automation", Proceedings IEEE International Conference on Defect and Fault Tolerance in VLSI Systems, pp 59-67, 1996; and PA1 M. Lorenzetti, "The Effect of Channel Router Algorithms on Chip Yield," Proceedings of International Workshop on Layout Synthesis, May 1990. PA1 1) Channel routing, wherein the router connects all the nets, allowing for an increase of the area taken by the wiring to achieve all the connections, and PA1 2) Area routing, wherein the router is given a fixed area to connect all the nets. PA1 E. P. Huijbregts, H. Xue and J. A. G. Jess, "Routing for Reliable Manufacturing", IEEE Transactions on Semiconductor Manufacturing, vol. 8, pp 188-194, 1995.
A conventional Detailed Routing can be achieved by following one of two approaches:
The above listed references generally describe various methods which apply exclusively to channel routing, (as opposed to area routing). Channel routing techniques are mostly interesting as a research tool but are seldom used in practice, mainly because of the aforementioned wiring versus area tradeoff.
Within the context of area routing, attempts have been made to improve yield while wiring a chip, module, and the like. Such an approach is described in an article by:
The above mentioned article by E. P. Huijbregts et al., is of particular interest since formulae are developed that measure yield effects as a function of wire length, common run length, and wiring crossing areas. These formulae are then combined with the traditional steiner tree routing objective (which is the same objective used for maze routing), using a scaled weight (or cost) proportional to the sparsity of the circuit. Using these formulae, the maze routing expansion method is modified to include the region surrounding the wire to compute the cost of the wire. Yet, the method described by E. P. Huijbregts et al. includes complex formulae to derive the weights which control the maze runner. This approach suffers from certain fundamental limitations, such as the applicability of these formulae which depend on assumptions made about the manufacturing model and the design which are not generally applicable. Further, the method requires modifying the core of the maze router, which results in a severe performance penalty.